package com.lw.leetcode.arr;

/**
 * 264. 丑数 II
 *
 * @Author liw
 * @Date 2021/5/7 10:31
 * @Version 1.0
 */
public class NthUglyNumber {
    public int nthUglyNumber(int n) {
        if (n < 7) {
            return n;
        }
        int[] arr = new int[n + 1];
        int a = 4;
        int b = 3;
        int c = 2;
        arr[1] = 1;
        arr[2] = 2;
        arr[3] = 3;
        arr[4] = 4;
        arr[5] = 5;
        arr[6] = 6;
        for (int i = 7; i <= n; i++) {
            int a1 = arr[a] << 1;
            int b1 = arr[b] * 3;
            int c1 = arr[c] * 5;
            arr[i] = Math.min(Math.min(a1,b1), c1);
            if (arr[i] == a1) {
                a++;
            }
            if (arr[i] == b1) {
                b++;
            }
            if (arr[i] == c1) {
                c++;
            }
        }
        return arr[n];
    }
}
